{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Coin Path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cheapestJump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #金币路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组 <code>A</code>（下标从 <code>1</code> 开始）包含 N 个整数：A<sub>1</sub>，A<sub>2</sub>，&hellip;&hellip;，A<sub>N</sub>&nbsp;和一个整数 <code>B</code>。你可以从数组 <code>A</code> 中的任何一个位置（下标为 <code>i</code>）跳到下标&nbsp;<code>i+1</code>，<code>i+2</code>，&hellip;&hellip;，<code>i+B</code>&nbsp;的任意一个可以跳到的位置上。如果你在下标为 <code>i</code> 的位置上，你需要支付 A<sub>i</sub> 个金币。如果 A<sub>i</sub> 是 -1，意味着下标为 <code>i</code> 的位置是不可以跳到的。</p>\n",
    "\n",
    "<p>现在，你希望花费最少的金币从数组 <code>A</code> 的 <code>1</code> 位置跳到&nbsp;<code>N</code> 位置，你需要输出花费最少的路径，依次输出所有经过的下标（从 1 到 N）。</p>\n",
    "\n",
    "<p>如果有多种花费最少的方案，输出字典顺序最小的路径。</p>\n",
    "\n",
    "<p>如果无法到达 N 位置，请返回一个空数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>样例 1 :</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> [1,2,4,-1,2], 2\n",
    "<strong>输出:</strong> [1,3,5]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>样例 2 :</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> [1,2,4,-1,2], 1\n",
    "<strong>输出:</strong> []\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注释 :</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>路径 Pa<sub>1</sub>，Pa<sub>2</sub>，&hellip;&hellip;，Pa<sub>n&nbsp;</sub>是字典序小于 Pb<sub>1</sub>，Pb<sub>2</sub>，&hellip;&hellip;，Pb<sub>m&nbsp;</sub>的，当且仅当第一个 Pa<sub>i</sub> 和 Pb<sub>i</sub> 不同的 <code>i</code> 满足 Pa<sub>i</sub> &lt; Pb<sub>i</sub>，如果不存在这样的 <code>i</code> 那么满足 <code>n</code> &lt; <code>m</code>。</li>\n",
    "\t<li>A<sub>1</sub> &gt;= 0。&nbsp;A<sub>2</sub>, ..., A<sub>N</sub>&nbsp;（如果存在）&nbsp;的范围是 [-1, 100]。</li>\n",
    "\t<li>A 数组的长度范围 [1, 1000].</li>\n",
    "\t<li>B 的范围&nbsp;[1, 100].</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [coin-path](https://leetcode.cn/problems/coin-path/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [coin-path](https://leetcode.cn/problems/coin-path/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4,-1,2]\\n2', '[1,2,4,-1,2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        n = len(coins)\n",
    "        if n == 1:\n",
    "            return [1] \n",
    "        dp = [float('inf')] * n \n",
    "        g = [-1] * n \n",
    "        dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            if coins[i] == -1:\n",
    "                continue \n",
    "            for j in range(max(0, i-maxJump), i):\n",
    "                if dp[j] == float('inf'):\n",
    "                    continue \n",
    "                if dp[j] + coins[j] < dp[i]:\n",
    "                    dp[i] = dp[j] + coins[j] \n",
    "                    g[i] = j \n",
    "                elif dp[j] + coins[j] == dp[i]:\n",
    "                    arr1=[i+1]\n",
    "                    p1 = j \n",
    "                    while p1 >= 0:\n",
    "                        arr1.append(p1+1) \n",
    "                        p1 = g[p1] \n",
    "                    arr2 = []\n",
    "                    p2 = i \n",
    "                    while p2 >= 0:\n",
    "                        arr2.append(p2+1)\n",
    "                        p2 = g[p2] \n",
    "                    #print('*', i, j)\n",
    "                    #print(j, arr1[::-1]) \n",
    "                    #print(g[i], arr2[::-1])\n",
    "                    if arr1[::-1] <= arr2[::-1]:\n",
    "                        g[i] = j \n",
    "        #print(g)\n",
    "        #print(dp) \n",
    "        if g[-1] == -1:\n",
    "            return [] \n",
    "        arr = []\n",
    "        p = n-1 \n",
    "        while p >= 0:\n",
    "            arr.append(p+1) \n",
    "            p = g[p]\n",
    "        return arr[::-1] \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        n = len(coins) \n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        if coins[-1] == -1:\n",
    "            return [] \n",
    "        dp = [float('inf')] * n \n",
    "        g = [-1] * n \n",
    "        g[-1] = n\n",
    "        dp[-1] = 0 \n",
    "        coins[0] = 0 \n",
    "        for i in range(n-2, -1, -1):\n",
    "            if coins[i] == -1:\n",
    "                continue \n",
    "            for j in range(i+1, min(i+maxJump, n-1) + 1):\n",
    "                if dp[j] == float('inf'):\n",
    "                    continue \n",
    "                if dp[j] + coins[j] < dp[i]:\n",
    "                    dp[i] = dp[j] + coins[j] \n",
    "                    g[i] = j \n",
    "        if dp[0] == float('inf'):\n",
    "            return [] \n",
    "        arr = []\n",
    "        p = 0 \n",
    "        while p < n:\n",
    "            arr.append(p+1)\n",
    "            p = g[p]\n",
    "        return arr "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, A: List[int], maxJump: int) -> List[int]:\n",
    "        N = len(A)\n",
    "        dp = [ float(\"inf\") for _ in range(N+1) ]\n",
    "        dp[0] = 0\n",
    "        dp[1] = A[0] if A[0] != -1 else float(\"inf\")\n",
    "        parents = [ \"\" for _ in range(N+1) ]\n",
    "        parents[1] = \"1\"\n",
    "        for i in range(2, 1+N):\n",
    "            if A[i-1] == -1:\n",
    "                continue\n",
    "            for j in range(i-1, max(i-maxJump-1, 0), -1):\n",
    "                if dp[j] + A[i-1] < dp[i]:\n",
    "                    dp[i], parents[i] = dp[j] + A[i-1], parents[j] + \",\" + str(i)\n",
    "                elif dp[j] + A[i-1] == dp[i]:\n",
    "                    T1, T2 = (parents[j] + \",\" + str(i)).split(\",\"), parents[i].split(\",\")\n",
    "                    N1, N2 = len(T1), len(T2)\n",
    "                    for k in range(min(N1, N2)):\n",
    "                        # print(T1[k], T2[k])\n",
    "                        if T1[k] and T2[k]:\n",
    "                            if int(T1[k]) == int(T2[k]):\n",
    "                                continue\n",
    "                            elif int(T1[k]) < int(T2[k]):\n",
    "                                # print(parents[j] + str(i), parents[i], T1[k], T2[k] )\n",
    "                                parents[i] = parents[j]  + \",\" +  str(i)\n",
    "                                break\n",
    "                            else:\n",
    "                                break\n",
    "        ret = []\n",
    "        for i in parents[N].split(\",\"):\n",
    "            if i:\n",
    "                ret.append(int(i))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        n=len(coins)\n",
    "        dp=[[float('inf'),[]] for _ in range(n)]\n",
    "        dp[0]=[coins[0],[1]]\n",
    "        for i in range(n):\n",
    "            for j in range(1,maxJump+1):\n",
    "                t=i+j\n",
    "                if t<n and coins[t]!=-1:\n",
    "                    tmp=dp[i][1]+[t+1]\n",
    "                    v=dp[i][0]+coins[t]\n",
    "                    if v<dp[t][0]:\n",
    "                        dp[t][0]=v\n",
    "                        dp[t][1]=tmp \n",
    "                    elif v==dp[t][0]:\n",
    "                        if tmp<dp[t][1]:\n",
    "                            dp[t][1]=tmp\n",
    "      #  print(dp)\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "\n",
    "        n = len(coins)\n",
    "        # Initialize the dp array with infinity and set dp[1] = coins[1]\n",
    "        dp = [float('inf')] * n\n",
    "        dp[0] = coins[0]\n",
    "\n",
    "        # Initialize paths list to store the path to each index\n",
    "        paths = [[] for _ in range(n)]\n",
    "        paths[0] = [1]\n",
    "\n",
    "        # Priority Queue to store (cost, index) and prioritize lower cost\n",
    "        pq = [(coins[0], 0)]\n",
    "\n",
    "        while pq:\n",
    "            cost, idx = heapq.heappop(pq)\n",
    "\n",
    "            # Skip if this is not the minimum cost to reach this index\n",
    "            if cost > dp[idx]:\n",
    "                continue\n",
    "\n",
    "            for k in range(1, maxJump + 1):\n",
    "                next_idx = idx + k\n",
    "\n",
    "                if next_idx >= n:\n",
    "                    break\n",
    "\n",
    "                # Skip if the index is not visitable\n",
    "                if coins[next_idx] == -1:\n",
    "                    continue\n",
    "\n",
    "                new_cost = cost + coins[next_idx]\n",
    "                # Update the dp and paths if a lower cost path is found\n",
    "\n",
    "                if new_cost < dp[next_idx]:\n",
    "                    dp[next_idx] = new_cost\n",
    "                    paths[next_idx] = paths[idx] + [next_idx + 1]\n",
    "                    heapq.heappush(pq, (new_cost, next_idx))\n",
    "                elif new_cost == dp[next_idx]:\n",
    "                    # Update the path if the cost is equal but the path is lexicographically smaller\n",
    "                    if paths[idx] + [next_idx + 1] < paths[next_idx]:\n",
    "                        paths[next_idx] = paths[idx] + [next_idx + 1]\n",
    "                        heapq.heappush(pq, (new_cost, next_idx))\n",
    "\n",
    "\n",
    "        # Return the path to reach index n if it's reachable, otherwise return an empty array\n",
    "        return paths[-1] if dp[-1] != float('inf') else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        n=len(coins)\n",
    "        dp=[[float(\"inf\"),[]]for _ in range(n)]\n",
    "        dp[0]=[0,[1]]\n",
    "        for i in range(1,n):\n",
    "            if coins[i]==-1:\n",
    "                continue\n",
    "            for j in range(max(0,i-maxJump),i):\n",
    "                if dp[i][0]>dp[j][0]+coins[i]:\n",
    "                    dp[i][0]=dp[j][0]+coins[i]\n",
    "                    dp[i][1]=copy.deepcopy(dp[j][1])+[i+1]\n",
    "                elif dp[i][0]!=float(\"inf\") and dp[i][0]==dp[j][0]+coins[i]:\n",
    "                    tp=copy.deepcopy(dp[j][1])+[i+1]\n",
    "                    if dp[i][1]>tp:\n",
    "                        dp[i][1]=tp\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        n=len(coins)\n",
    "        dp=[[float(\"inf\"),[]]for _ in range(n)]\n",
    "        dp[0]=[0,[1]]\n",
    "        for i in range(1,n):\n",
    "            if coins[i]==-1:\n",
    "                continue\n",
    "            #dp[i]=min(dp[max(0,i-maxJump):i])\n",
    "            for j in range(max(0,i-maxJump),i):\n",
    "               #print(j,dp[i][0])\n",
    "                if dp[i][0]>dp[j][0]+coins[i]:\n",
    "                    dp[i][0]=dp[j][0]+coins[i]\n",
    "                    dp[i][1]=copy.deepcopy(dp[j][1])+[i+1]\n",
    "                elif dp[i][0]!=float(\"inf\") and dp[i][0]==dp[j][0]+coins[i]:\n",
    "                    tp=copy.deepcopy(dp[j][1])+[i+1]\n",
    "                    if dp[i][1]>tp:\n",
    "                        dp[i][1]=tp\n",
    "            #if dp[i][0]==float(\"inf\"):\n",
    "            #    continue\n",
    "            #print(i,dp[i])\n",
    "            #dp[i]=copy.deepcopy(dp[i])\n",
    "            #dp[i][0]+=coins[i]\n",
    "            #dp[i][1]+=[i+1]\n",
    "        print(dp)\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        n = len(coins)\n",
    "\n",
    "        def check(a,  b):\n",
    "            n = min(len(a), len(b))\n",
    "            for i in range(n):\n",
    "                if a[i] > b[i]:\n",
    "                    return True\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < n and coins[i] == -1:\n",
    "                return inf, []\n",
    "            if i == n - 1:\n",
    "                return 0, [n]\n",
    "            cur_dis = inf\n",
    "            cur_path = []\n",
    "            for p in range(1, maxJump + 1):\n",
    "                if i + p < n:\n",
    "                    dis, path = dfs(i+p)\n",
    "                    dis += coins[i]\n",
    "                    if dis < cur_dis:\n",
    "                        cur_dis = dis\n",
    "                        cur_path = path\n",
    "                    elif dis == cur_dis and check(cur_path, path):\n",
    "                        cur_path = path\n",
    "            return cur_dis, [i+1] + cur_path\n",
    "\n",
    "                        \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "        cur, path = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        if cur < inf:\n",
    "            return path\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        if coins[0] == -1 or coins[-1] == -1:\n",
    "            return []\n",
    "        n = len(coins)\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        cost = [inf]*n\n",
    "        path = [[n + 1] for i in range(n)] #路径全部初始化为字典序最大\n",
    "        cost[0] = 0\n",
    "        q = [(0,[1],0)]\n",
    "        # 路径字典序比较\n",
    "        def cmp_arr(a,b):\n",
    "            i = j = 0\n",
    "            while i < len(a) and j < len(b):\n",
    "                if a[i] > b[j]:\n",
    "                    return 1\n",
    "                elif a[i] < b[j]:\n",
    "                    return -1\n",
    "                i += 1\n",
    "                j += 1\n",
    "            return len(a) - len(b)\n",
    "\n",
    "        while q:\n",
    "            c,p,i = heappop(q) # 花费，路径，位置\n",
    "            if c > cost[i] or (c == cost[i] and cmp_arr(p, path[i]) > 0): \n",
    "                continue\n",
    "            for j in range(i + 1,min(i + maxJump + 1,n)):\n",
    "                if coins[j] == -1:\n",
    "                    continue\n",
    "                if c + coins[i] < cost[j] or (c + coins[i] == cost[j] and cmp_arr(p + [j + 1],path[j]) < 0):\n",
    "                    cost[j] = c + coins[i]\n",
    "                    path[j] = p + [j + 1]\n",
    "                    heappush(q,(c + coins[i],p + [j + 1],j))\n",
    "        return path[-1] if path[-1] != [n + 1] else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        if coins[0] == -1 or coins[-1] == -1:\n",
    "            return []\n",
    "        n = len(coins)\n",
    "        if n == 1:\n",
    "            return [1]\n",
    "        cost = [inf]*n\n",
    "        path = [[n + 1] for i in range(n)]\n",
    "        cost[0] = 0\n",
    "        q = [(0,[1],0)]\n",
    "        def cmp_arr(a,b):\n",
    "            i = j = 0\n",
    "            while i < len(a) and j < len(b):\n",
    "                if a[i] > b[j]:\n",
    "                    return 1\n",
    "                elif a[i] < b[j]:\n",
    "                    return -1\n",
    "                i += 1\n",
    "                j += 1\n",
    "            return len(a) - len(b)\n",
    "\n",
    "        while q:\n",
    "            c,p,i = heappop(q)\n",
    "            if c > cost[i] or (c == cost[i] and cmp_arr(p, path[i]) > 0): \n",
    "                continue\n",
    "            \n",
    "            # if i == n - 1:\n",
    "            #     return [x + 1 for x in p + [i]]\n",
    "            \n",
    "            for j in range(i + 1,min(i + maxJump + 1,n)):\n",
    "                if coins[j] != -1:\n",
    "                    if c + coins[i] < cost[j] or (c + coins[i] == cost[j] and cmp_arr(p + [j + 1],path[j]) < 0):\n",
    "                        cost[j] = c + coins[i]\n",
    "                        path[j] = p + [j + 1]\n",
    "                        heappush(q,(c + coins[i],p + [j + 1],j))\n",
    "        return path[-1] if path[-1] != [n + 1] else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param coins:\n",
    "        :param maxJump:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def to_str(ll):\n",
    "            return \"\".join([str(i) for i in ll])\n",
    "\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_path(idx):\n",
    "            if idx == 0:\n",
    "                return coins[0], [0]\n",
    "            val = math.inf\n",
    "            idx_list = []\n",
    "            for i in range(1, maxJump + 1):\n",
    "                if idx - i < 0:\n",
    "                    break\n",
    "                prev_val = coins[idx - i]\n",
    "                if prev_val == -1:\n",
    "                    continue\n",
    "                val1, idxlist = get_min_path(idx - i)\n",
    "                if val1 < val:\n",
    "                    val = val1\n",
    "                    idx_list = idxlist\n",
    "                elif val1 == val:\n",
    "                    if idxlist + [idx] < idx_list + [idx]:\n",
    "                        idx_list = idxlist\n",
    "            return val + coins[idx], idx_list + [idx]\n",
    "\n",
    "        if coins[-1] == -1:\n",
    "            return []\n",
    "        val, idx_list = get_min_path(len(coins) - 1)\n",
    "        if val == math.inf:\n",
    "            return []\n",
    "        return [i + 1 for i in idx_list]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        :param coins:\n",
    "        :param maxJump:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_min_path(idx):\n",
    "            if idx == 0:\n",
    "                return coins[0], [0]\n",
    "            val = math.inf\n",
    "            idx_list = []\n",
    "            for i in range(1, maxJump + 1):\n",
    "                if idx - i < 0:\n",
    "                    break\n",
    "                prev_val = coins[idx - i]\n",
    "                if prev_val == -1:\n",
    "                    continue\n",
    "                val1, idxlist = get_min_path(idx - i)\n",
    "                if val1 < val:\n",
    "                    val = val1\n",
    "                    idx_list = idxlist\n",
    "                elif val1 == val:\n",
    "                    if idxlist + [idx] < idx_list + [idx]:\n",
    "                        idx_list = idxlist\n",
    "            return val + coins[idx], idx_list + [idx]\n",
    "\n",
    "        if coins[-1] == -1:\n",
    "            return []\n",
    "        val, idx_list = get_min_path(len(coins) - 1)\n",
    "        if val == math.inf:\n",
    "            return []\n",
    "        return [i + 1 for i in idx_list]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        if coins[0] == -1 or coins[-1] == -1:\n",
    "            return []\n",
    "        n = len(coins)\n",
    "        cost = [inf]*n\n",
    "        #cost[0] = 0\n",
    "        q = [(0,[1])]\n",
    "        while q:\n",
    "            dis,path = heappop(q)\n",
    "            i = path[-1] - 1\n",
    "            if dis >= cost[i]:\n",
    "                continue\n",
    "            if i == n - 1:\n",
    "                return path\n",
    "            cost[i] = dis\n",
    "            for j in range(i + 1,min(i + maxJump + 1,n)):\n",
    "                if coins[j] != -1:\n",
    "                    heappush(q,(dis + coins[i],path + [j + 1]))\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:\n",
    "        if coins[0] == -1 or coins[-1] == -1:\n",
    "            return []\n",
    "        n = len(coins)\n",
    "        cost = [inf]*n\n",
    "        q = [(0,[1])]\n",
    "        while q:\n",
    "            dis,path = heappop(q)\n",
    "            i = path[-1] - 1\n",
    "            if dis >= cost[i]:\n",
    "                continue\n",
    "            if i == n - 1:\n",
    "                return path\n",
    "            cost[i] = dis\n",
    "            for j in range(i + 1,min(i + maxJump + 1,n)):\n",
    "                if coins[j] != -1:\n",
    "                    heappush(q,(dis + coins[i],path + [j + 1]))\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cheapestJump(self, a: List[int], b: int) -> List[int]:\n",
    "        n = len(a)\n",
    "        if n==1:\n",
    "            return [1]\n",
    "        s = [[0, 1]]\n",
    "        heapq.heapify(s)\n",
    "\n",
    "        v = set()\n",
    "        while s:\n",
    "            tmp = heapq.heappop(s)\n",
    "            # val = [0]\n",
    "            i = tmp[-1]\n",
    "            if i in v:\n",
    "                continue \n",
    "            if i==n:\n",
    "                return tmp[1:]\n",
    "            v.add(i)\n",
    "            for j in range(i, i+b):\n",
    "                if j<n:\n",
    "                    if a[j]!=-1:\n",
    "                        tmp1 = tmp[::]\n",
    "                        tmp1[0] += a[i-1] \n",
    "                        tmp1.append(j+1)\n",
    "                        heapq.heappush(s, tmp1) \n",
    "        return []\n",
    "\n",
    "                \n",
    "            \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
